# -*- coding: utf-8 -*-

"""
implement DEFLATE algorithm
DEFLATE is a lossless data compression algorithm that uses a combination of
the LZ77 algorithm and Huffman coding.

A Deflate stream consists of a series of blocks. Each block is preceded by a
3-bit header:

* 1-bit: Last block in stream marker:

  - 1: this is the last-block in the stream.
  - 0: there are more blocks to precess after this one.

* 2-bits: Encoding method used for this block type:

  - 00: a stored/raw/literal section follows, between 0 and 65,535 bytes in
    length.

  - 01: a static Huffman compressed block, using a pre-agreeded Huffman tree.
  - 10: a compressed block complete with the Huffman table supplied.
  - 11: reserved, don't use.

DEFLATE RFC 1951
================

However, it disallows random access to compressed data;

for English text, usually compressed by a factor of 2.5 to 3.

Intended audience
=================

The Huffman trees for each block are independent of those for previous or
subsequent blocks; the LZ77 algorithm may use a reference to a duplicated
string occuring in a previous block, up to 32K input bytes before.

Each block consists of two parts: a pair of Huffman code trees that describe
the representation of the compressed data part, and a compressed data part.l
"""




